#include <bits/stdc++.h>
using namespace std;
// dp[i][j],j=0末尾两位相等，j=1末尾两位不相等
/*符合条件的字符串数量=dp[i][0]+dp[i][1]
dp[i][0]=dp[i-1][1],dp[i][1]=dp[i-1][1]+dp[i-1][0]*/
#define int long long //将int替换为long long。这样在代码中所有出现的int都会被替换为long long，从而扩大整数类型的范围，避免溢出问题。
const int mod = 1e9 + 7;
int f, n, dp[1000005][2];
signed main() //
{
	dp[1][0] = 0, dp[1][1] = 3; //
	for (int i = 2; i <= 100000; i++)
	{
		dp[i][0] = dp[i - 1][1];
		dp[i][1] = 2 * (dp[i - 1][0] + dp[i - 1][1]) % mod;
	}
	cin >> f;
	while (f--)
	{
		cin >> n;
		cout << (dp[n][0] + dp[n][1]) % mod << endl;
	}

	return 0;
}